package com.xiaoyu.binaryTree;

/**
 * @program: DS_and_A
 * @description:
 * 给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。
 *
 * 高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。
 *
 * 输入：nums = [-10,-3,0,5,9]
 * 输出：[0,-3,9,-10,null,5]
 * 解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案
 *
 *
 *  AVL定义:不仅仅是根结点为AVL,整个树的所有的子树都必须是AVL
 *
 * @author: YuWenYi
 * @create: 2021-05-18 09:14
 **/
public class ArrSortedArrayToBST_108 {

    //自己的思路:最后创建出来的树只能保证根结点是AVL树,但是其他结点不一定满足AVL树,因此它不是AVL树,所有写错了!
    public TreeNode sortedArrayToBST1(int[] nums) {
        TreeNode root = new TreeNode(nums[0]);
        TreeNode resNode = root;
        //按照二叉排序树的规则,小在左大在右,构建一颗树
        for (int i = 1; i < nums.length; i++) {
            TreeNode node = new TreeNode(nums[i]);
            root.right = node;
            root = node;
            if (height(resNode.right) - height(resNode.left) > 1){
                //创建新结点
                TreeNode newNode = new TreeNode(resNode.val);
                newNode.left = resNode.left;
                newNode.right = resNode.right.left;
                //改头结点
                resNode.val = resNode.right.val;
                resNode.right = resNode.right.right;
                resNode.left = newNode;
            }
        }
        return resNode;
    }
    public int height(TreeNode node){
        if (node == null){
            return 0;
        }
        return Math.max(node.left == null ? 0 : height(node.left), node.right == null ? 0 : height(node.right)) + 1;
    }



    //取中间结点,中间结点的左边构建左子树,中间结点的右边构建右子树
    public TreeNode sortedArrayToBST(int[] nums) {
        return dfs(nums, 0, nums.length-1);
    }

    public TreeNode dfs(int[] nums,int left,int right){
        if (left > right){
            return null;
        }
        int mid = (left + right) / 2;
        TreeNode node = new TreeNode(nums[mid]);

        node.left = dfs(nums, left, mid-1);
        node.right = dfs(nums, mid+1, right);

        return node;
    }

    public static void main(String[] args) {
        ArrSortedArrayToBST_108 sb = new ArrSortedArrayToBST_108();
        int[] arr = new int[]{0,1,2,3,4};
        TreeNode node = sb.sortedArrayToBST(arr);

        System.out.println(Inorder_94.inorderTraversal(node));
    }
}
